export default class BST {
  constructor() {
    this.root = null;
  }

  /**
   * 判断两个二叉树是否相同
   * @param node1
   * @param node2
   * @returns {*}
   */
  static isSameTree(node1, node2) {
    if (node1 == null && node2 == null) return true;
    if (node1 == null || node2 == null) return false;
    if (node1.data !== node2.data) return false;

    return BST.isSameTree(node1.left, node2.left) && BST.isSameTree(node1.right, node2.right);
  }

  /**
   * 判断一个对象是否是二叉树
   * @param node {必传}
   * @param min
   * @param max
   * @returns {*}
   */
  static isValidBST(node, min, max) {
    if (node == null) return true;
    if (node.data > max || node.data < min) return false;
    return BST.isValidBST(node.left, min, node.data) && BST.isValidBST(node.right, node.data, max);
  }

  generatorNode(data) {
    return {
      data,
      left: null,
      right: null
    }
  }

  /**
   * 插入
   * @param data
   * @returns {BST}
   */
  insert (data) {
    const node = this.generatorNode(data);
    if (this.root == null) {
      this.root = node;
      return this;
    }

    let currentNode = this.root;
    while (true) {
      if (data < currentNode.data) {
        if (currentNode.left == null) {
          currentNode.left = node;
          break;
        } else {
          currentNode = currentNode.left;
        }
      } else {
        if (currentNode.right == null) {
          currentNode.right = node;
          break;
        } else {
          currentNode = currentNode.right;
        }
      }
    }
    return this;
  }

  /**
   * 搜索
   * @param data
   * @param currentNode
   * @returns {*}
   */
  search (data, currentNode) {
    if (this.root === undefined || currentNode === null) return null;
    currentNode = currentNode || this.root;
    if (currentNode.data === data) {
      return currentNode;
    } else if (currentNode.data > data) {
      return this.search(data, currentNode.left || null);
    } else {
      return this.search(data, currentNode.right || null);
    }
    return null;
  }

  /**
   * 找最小值的节点
   * @param currentNode
   * @returns {*}
   */
  findMin(currentNode) {
    currentNode = currentNode || this.root;
    return currentNode.left == null ? currentNode : this.findMin(currentNode.left);
  }

  /**
   * 找最大值的节点
   * @param currentNode
   * @returns {*}
   */
  findMax(currentNode) {
    currentNode = currentNode || this.root;
    return currentNode.right == null ? currentNode : this.findMax(currentNode.right);
  }

  /**
   * 删除节点
   * @param data 需要删除的值 {必传}
   * @param currentNode 从哪个节点开始遍历 {选传}
   * @returns {*}
   */
  delete(data, currentNode = this.root) {
    if (currentNode == null) return null;
    if (currentNode.data === data) {
      // 这两个 if 语句适用于两种情况：
      // 1. 待删除的节点为叶子节点，没有左右子节点，直接删除（return null）
      // 2. 待删除节点仅有一个叶子节点，就用该子节点替换它
      if (currentNode.left == null) return currentNode.right;
      if (currentNode.right == null) return currentNode.left;
      // 待删除的节点有左右子节点，可行的方法：
      // 1. 从待删除节点开始，找到左子树上最大的节点，替换它
      // 2. 从待删除节点开始，找到右子树上最小的节点，替换它
      // 这边采用第二种方式
      // 找到右子树最小节点
      const minNode = this.findMin(currentNode.right);
      // 把当前 currentNode 的值改成 minNode 的值
      currentNode.data = minNode.data;
      // 删除 minNode
      currentNode.right = this.delete(minNode.data, currentNode.right);
    } else if (currentNode.data > data) {
      currentNode.left = this.delete(data, currentNode.left);
    } else {
        currentNode.right = this.delete(data, currentNode.right);
    }
    return currentNode;
  }

  /**
   * 前序遍历
   * @param node
   * @returns {boolean}
   */
  preorder(node) {
    if (node == null) return false;
    console.log(node.data);
    this.preorder(node.left);
    this.preorder(node.right);
  }

  /**
   * 中序遍历
   * @param node
   * @returns {boolean}
   */
  inorder(node) {
    if (node == null) return false;
    this.inorder(node.left);
    console.log(node.data);
    this.inorder(node.right);
  }

  /**
   * 后序遍历
   * @param node
   * @returns {boolean}
   */
  lastorder(node) {
    if (node == null) return false;
    this.lastorder(node.left);
    this.lastorder(node.right);
    console.log(node.data);
  }

  getBst() {
    return this.root;
  }
}


